package com.nine.algorithm.leetcode.list;

/**
 * @author nine
 * @version 1.0
 * @description 反转链表
 * @date 24/5/3 22:54
 */
public class Leetcode206 {

	public static void main(String[] args) {
		ListNode o5 = new ListNode(5, null);
		ListNode o4 = new ListNode(4, o5);
		ListNode o3 = new ListNode(3, o4);
		ListNode o2 = new ListNode(2, o3);
		ListNode o1 = new ListNode(1, o2);

		System.out.println(o1);
		// ListNode n1 = reverseList(o1);
		// System.out.println("方法一：" + n1);
		// ListNode n2 = reverseList2(o1);
		// System.out.println("方法二：" + n2);
		// ListNode n3 = reverseList3(o1);
		// System.out.println("方法三：" + n3);
		// ListNode n4 = reverseList4(o1);
		// System.out.println("方法四：" + n4);
		ListNode n5 = reverseList5(o1);
		System.out.println("方法五：" + n5);
	}

	/**
	 * 方法一：构造一个新链表，从旧链表依次拿到每一个节点，创建新节点并添加到新链表头部，完成之后新链表就是倒序的
	 * 1 2 3 4 5 ->
	 * 5 4 3 2 1
	 *
	 * @param o1 旧链表
	 * @return 新链表
	 */
	private static ListNode reverseList(ListNode o1) {
		if (o1 == null) {
			return null;
		}
		ListNode n1 = null;
		ListNode p = o1;
		while (p != null) {
			n1 = new ListNode(p.val, n1);
			// 移动到下一指针
			p = p.next;
		}
		return n1;
	}

	/**
	 * 方法二：构造一个新链表，从旧链表头部移除节点，添加到新链表头部，完成之后新链表倒序。
	 * 区别在于：原题目未提供节点外层容器类，这里提供一个，另外一个区别是并不去构造新节点。
	 *
	 * @return 新链表
	 */
	private static ListNode reverseList2(ListNode head) {
		List o1 = new List(head);
		List n1 = new List(null);
		while (o1.head != null) {
			// o1一直在remove，最终一定会退出循环
			ListNode first = o1.removeFirst();
			n1.addFirst(first);
		}
		return n1.head;
	}

	/**
	 * 方法三：递归
	 * 1 2 3 4 5 -> 依次进去，当最后一个5进去时，直接返回当前节点，然后递归依次结束，
	 * 此时p=4，p.next=5，需要将当前节点，即p=4的next节点的下一个节点设置为当前节点，实现反转
	 * 即 4.next.next = 4 [5.next=4]，4.next = null
	 *
	 * @param p 节点 [1,2,3,4,5]
	 * @return 节点  [5,4,3,2,1]
	 */
	public static ListNode reverseList3(ListNode p) {
		// 如果当前节点为空，或者已达到链表末尾（即当前节点的下一个节点为空），则返回该节点作为新的头节点
		if (p == null || p.next == null) {
			return p;
		}
		ListNode last = reverseList3(p.next);
		// 将当前节点的下一个节点的 next 指针指向当前节点，实现反转
		p.next.next = p;
		// 将当前节点的 next 指针置为空，防止循环链表的产生
		p.next = null;
		return last;
	}

	/**
	 * 方法四：新旧指针
	 * o1  o2
	 * 1   2   3   4   5
	 * n1
	 * o2  o1
	 * 2   1   3   4   5
	 * n1
	 *
	 * @param o1 旧的链表
	 * @return
	 */
	public static ListNode reverseList4(ListNode o1) {
		// 边界处理
		if (o1 == null || o1.next == null) {
			return o1;
		}
		// o2是o1的下一个节点
		ListNode o2 = o1.next;
		// 新链表，指向和o1相同的节点
		ListNode n1 = o1;
		while (o2 != null) {
			// 将o1.next，不再指向o2，而是指向o2.next【也就是将o2从链表移除】
			o1.next = o2.next;
			// 将o2从链表移除之后，放到链表的头节点
			o2.next = n1;
			// n1移至o2的位置
			n1 = o2;
			// 再将o2移回到o1后面
			o2 = o1.next;
		}
		return n1;
	}


	/**
	 * 方法五：新旧链表，新旧指针
	 * o1  o2
	 * 1   2   3   4   5
	 *
	 * @param o1
	 * @return
	 */
	public static ListNode reverseList5(ListNode o1) {
		// 边界处理
		if (o1 == null || o1.next == null) {
			return o1;
		}
		ListNode n1 = null;
		while (o1 != null) {
			// o1的下一节点为o2节点
			ListNode o2 = o1.next;
			// o1的下一节点指向n1节点
			o1.next = n1;
			// o1赋值给n1
			n1 = o1;
			// o2赋值给o1
			o1 = o2;
		}
		return n1;
	}

	static class List {
		ListNode head;

		public List(ListNode head) {
			this.head = head;
		}

		// 添加头节点
		public void addFirst(ListNode first) {
			first.next = head;
			head = first;
		}

		// 移除头节点
		public ListNode removeFirst() {
			ListNode first = head;
			if (first != null) {
				head = first.next;
			}
			return first;
		}
	}

}
